package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 347.前k个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案.
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 */
public class Num_347 {

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer,Integer> map = new HashMap<>();
        //先统计出现的次数
        for(int i : nums){
            //看map中是否已经存储了这个元素
            //根据key取出映射的value;若key不存在,则返回0
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        //创建优先级队列,基于最小堆
        Queue<Freq> queue = new PriorityQueue<>();
        //将Map集合转为Set集合，遍历一个个键值对
        //Map.Entry ：此接口中存储的就是一个个键值对对象，将key和value捆绑在一起
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(queue.size() < k){
                queue.offer(new Freq(entry.getKey(), entry.getValue()));
            }else if(entry.getValue() > queue.peek().getTimes()){
                //若遍历的当前元素 > 队首元素,则先将队首元素出队
                queue.poll();
                //再将当前元素入队
                queue.offer(new Freq(entry.getKey(), entry.getValue()));
            }
        }
        //返回结果
        int[] ret = new int[k];
        for(int i=0; i<k; i++){
            ret[i] = queue.poll().getNum();
        }
        return ret;
    }

    //自定义内部类存放元素和它的频次，并且具备比大小的功能
    private class Freq implements Comparable<Freq> {
        private int num;
        private int times;

        public Freq(int num, int times) {
            this.num = num;
            this.times = times;
        }

        public int getNum() {
            return num;
        }

        public int getTimes() {
            return times;
        }

        @Override
        public int compareTo(Freq o) {
            return this.times - o.times;
        }
    }
}
